package leetcode;

/*
559. N叉树的最大深度
给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
例如，给定一个 3叉树 :
我们应返回其最大深度，3。
*/

import java.util.ArrayList;
import java.util.List;

public class problems_559 {
    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        node3.children = new ArrayList<Node>(){{
            add(node5);
            add(node6);
        }};
        node1.children = new ArrayList<Node>(){{
            add(node2);
            add(node3);
            add(node4);
        }};
        System.out.println(new Solution().maxDepth(node1));
    }

    static class Node {
        public int val;
        public List<Node> children;
        public Node() {}
        public Node(int _val) { val = _val; }
        public Node(int _val, List<Node> _children) { val = _val;children = _children; }
    }
    static class Solution {
        public int maxDepth(Node root) {
            if(null == root) return 0;
            List<Node> layer = new ArrayList<>();
            layer.add(root);
            int num = 0;
            while (!layer.isEmpty()){
                num++;
                List<Node> next = new ArrayList<>();
                for (int i = 0; i < layer.size(); i++) {
                    if(null != layer.get(i) && null != layer.get(i).children) next.addAll(layer.get(i).children);
                }
                layer = next;
            }
            return num;
        }
    }
}